package leetcode;

/**
 * 采用 前序遍历的思想去解题
 */
public class l0114_二叉树展开为链表_前序遍历_迭代的方式_推荐使用这种 {

    public void flatten(TreeNode root) {
        //1 根
        //将左子树 嫁接到 右边
        while (root != null) {
            if (root.left != null) {
                //保留之前的right
                TreeNode oldRight = root.right;
                //将left 嫁接到right
                root.right = root.left;
                //清空left
                root.left = null;
                TreeNode mostRight = root;
                //将旧的right嫁接到右下角
                while (mostRight.right != null) {
                    mostRight = mostRight.right;
                }
                mostRight.right = oldRight;
            }
            //2 左子树  由于不存在左子树，故不需要遍历
            //3 右子树
            root = root.right;
        }
    }
}
